class BinaryTree:
    """二叉树"""
    class Node:
        """节点"""
        def __init__(self,data,left=None,right=None):
            self.data = data
            self.left = left
            self.right = right

    def __init__(self,data):
            self.root = self.Node(data)
            

    def append(self,data):
        """二叉树添加元素,默认优先添加左树"""
        rlist = [self.root] #模拟栈
        while True:
            q = rlist.pop()
            if not q.left:
                q.left = self.Node(data)
                return
            elif not q.right:
                q.right = self.Node(data)
                return
            else:
                if rlist == []:
                    rlist.append(q.right)
                    rlist.append(q.left)

    def append_left(self,node,data):
        """为一个节点添加左子树"""
        if node.left is None:
            node.left = self.Node(data)
        else:
            print('This node had left node')

    def append_right(self,node,data):
        """为一个节点添加右子树"""
        if node.right is None:
            node.right = self.Node(data)
        else:
            print('This node had right node')

    def order(self,node,flag=0):
        """遍历,0先序,1中序,2后序"""
        if node:
            if flag == 0:
                print(node.data,end=' ')
                self.order(node.left,flag)
                self.order(node.right,flag)
            elif flag == 1:
                self.order(node.left,flag)
                print(node.data,end=' ')
                self.order(node.right,flag)
            elif flag == 2:
                self.order(node.left,flag)
                self.order(node.right,flag)
                print(node.data,end=' ')

    def deep(self,node):
        """树的深度"""
        if node is None:
            return 0
        ldeep = self.deep(node.left)
        rdeep = self.deep(node.right)
        return max(ldeep,rdeep) + 1
    
    def per_iter_order(self,root):
        """非递归前序遍历"""
        stack = [root]
        while stack != [] :
            n = stack.pop()
            print(n.data, end=' ')
            if n.right:
                stack.append(n.right)
            if n.left:
                stack.append(n.left)
    
    def in_iter_order(self,root):
        """非递归中序遍历"""
        stack = []
        p = root
        while stack!=[] or p:
            if p:
                stack.append(p)
                p = p.left
            else:
                p = stack.pop()
                print(p.data,end=' ')
                p = p.right

    def post_iter_order(self,root):
        """非递归后序遍历"""
        stack = []
        p = root
        while True:
            while p:
                stack.append(p)
                p = p.left
            q = None
            while stack != []:
                p = stack.pop()
                if p.right == q :
                    print(p.data,end=' ')
                    q = p
                else:
                    stack.append(p)
                    p = p.right
                    break
            if stack == []:
                break
        
    def levelorder(self,root):
        """层次遍历"""
        queue = [root]
        result = []
        while queue != []:
            s = []
            level = len(queue)
            for i in range(level):
                n = queue.pop(0)
                s.append(n.data)
                if n.left:
                    queue.append(n.left)
                if n.right:
                    queue.append(n.right)
            result.append(s)
        print(result)



if __name__ == '__main__':
    t = BinaryTree(1)
    for i in range(2,8):
        t.append(i)
    # 先序
    t.order(t.root,0)
    print()
    t.per_iter_order(t.root)
    print('\n----------------')
    # 中序
    t.order(t.root,1)
    print()
    t.in_iter_order(t.root)
    print('\n----------------')
    # 后序
    t.order(t.root,2)
    print()
    t.post_iter_order(t.root)
    print('\n----------------')
    # 层次遍历
    t.levelorder(t.root)